package Hot100;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-12-20 11:01
 */
public class twoSum_3Sum_4Sum {

    /**
     * 1. 两数之和
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * 1、排序后双指针
     * 2、map记录出现过的元素以及其下标，挨个判断target-nums[i]是否存在
     * */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int cur=nums[i];
            if (map.containsKey(target-cur)){
                return new int[]{map.get(target-cur),i};
            }else {
                map.put(cur,i);
            }
        }
        return new int[]{-1,-1};
    }
    /** 两数之和，扩展
     * 找到所有的和为target的元素对，结果中的元素对不重复
     * */
    //twoSum找到所有的和为target的元素对
    List<List<Integer>> twoSum2(int[] nums, int target){
        Arrays.sort(nums);
        int left=0,right=nums.length-1;
        List<List<Integer>> res=new LinkedList<>();
        while (left<right){
            int sum=nums[left]+nums[right];
            int l=nums[left],r=nums[right];
            if (sum<target){
                while (left<right&&nums[left]==l)left++;
            }else if (sum>target){
                while (left<right&&nums[right]==r)right--;
            }else if (sum==target){
                LinkedList<Integer> list=new LinkedList<>();
                list.add(l);list.add(r);
                res.add(list);
                while (left<right&&nums[left]==l) left++;
                while (left<right&&nums[right]==r)right--;
            }
        }
        return res;
    }


    /**15. 三数之和
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     * 思路：《所有》
     * 1、回溯---会有重复：路径：已经选择过的元素
     * 选择列表：当前元素要还是不要
     * 终止条件：当路径中元素个数为3，或者nums到最后一个元素
     * 2、确定第一个数后，转换为两数之和
     * */
    List<List<Integer>> res15=new ArrayList<>();
    void backtrack15(int[] nums, int index, LinkedList<Integer> path,int sum){
        if (path.size()==3&&sum==0){
            res15.add(new LinkedList<>(path));
            return;
        }
        if (index==nums.length) return;
        //做出选择，要不要index元素
        path.add(nums[index]);
        backtrack15(nums,index+1,path,sum+nums[index]);
        path.removeLast();

        backtrack15(nums,index+1,path,sum);
    }
    public List<List<Integer>> threeSum1(int[] nums) {
        if (nums.length<3) return res15;
        backtrack15(nums,0,new LinkedList<>(),0);
        return res15;
    }


    //twoSum找到所有的和为target的元素对,nums已经有序，从start开始
    List<List<Integer>> twoSum1(int[] nums,int start,int target){
        //Arrays.sort(nums);
        int left=start,right=nums.length-1;
        List<List<Integer>> res=new LinkedList<>();
        while (left<right){
            int sum=nums[left]+nums[right];
            int l=nums[left],r=nums[right];
            if (sum<target){
                while (left<right&&nums[left]==l)left++;
            }else if (sum>target){
                while (left<right&&nums[right]==r)right--;
            }else if (sum==target){
                LinkedList<Integer> list=new LinkedList<>();
                list.add(l);list.add(r);
                res.add(list);
                while (left<right&&nums[left]==l) left++;
                while (left<right&&nums[right]==r)right--;
            }
        }
        return res;
    }
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        List<List<Integer>> res=new ArrayList<>();

        for (int i = 0; i < n; i++) {
            List<List<Integer>> twoSum1 = twoSum1(nums, i + 1, 0 - nums[i]);
            for (List<Integer> list:twoSum1) {
                list.add(nums[i]);
                res.add(list);
            }
            while (i<n-1&&nums[i]==nums[i+1]) i++;
        }
        return res;
    }

    /**18. 四数之和
     * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 
     * （若两个四元组元素一一对应，则认为两个四元组重复）：0 <= a, b, c, d < n，a、b、c 和 d 互不相同，   nums[a] + nums[b] + nums[c] + nums[d] == target
     *
     * 思路：穷举第一个数字，然后调用 3Sum 函数计算剩下三个数，最后组合出和为 target 的四元组。
     * */
    //修改3Sum从start开始，nums已经有序，选择和为target的三元组
    public List<List<Integer>> threeSum1(int[] nums,int start,int target) {
        int n=nums.length;
        List<List<Integer>> res=new ArrayList<>();

        for (int i = start; i < n; i++) {
            List<List<Integer>> twoSum1 = twoSum1(nums, i + 1, target - nums[i]);
            for (List<Integer> list:twoSum1) {
                list.add(nums[i]);
                res.add(list);
            }
            while (i<n-1&&nums[i]==nums[i+1]) i++;
        }
        return res;
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n=nums.length;
        List<List<Integer>> res=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<List<Integer>> listList = threeSum1(nums, i + 1, target - nums[i]);
            for (List<Integer> list:listList) {
                list.add(nums[i]);
                res.add(list);
            }
            while (i<n-1&&nums[i]==nums[i+1])i++;
        }
        return res;
    }

    /** n数之和
     * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回和为target且不重复的n元组
     * 总结上述过程，递归
     * */
    /* 注意：调用这个函数之前一定要先给 nums 排序 */
    List<List<Integer>> nSumTarget(int[] nums,int n,int start,int target){
        int sz=nums.length;
        List<List<Integer>> res=new LinkedList<>();
        if (n==2){
            //双指针
            int left=0,right=sz-1;
            while (left<right){
                int sum=nums[left]+nums[right];
                int l=nums[left],r=nums[right];
                if (sum<target){
                    while (left<right&&nums[left]==l)left++;
                }else if (sum>target){
                    while (left<right&&nums[right]==r)right--;
                }else if (sum==target){
                    LinkedList<Integer> list=new LinkedList<>();
                    list.add(l);list.add(r);
                    res.add(list);
                    while (left<right&&nums[left]==l) left++;
                    while (left<right&&nums[right]==r)right--;
                }
            }
        }else {
            //n>2递归计算（n-1）Sum
            for (int i = start; i < sz; i++) {
                List<List<Integer>> lists = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> list:lists) {
                    list.add(nums[i]);
                    res.add(list);
                }
                while (i<sz-1&&nums[i]==nums[i+1]) i++;
            }
        }
        return res;
    }

}
